Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Ich begrüße Sie herzlich zur Informationstheorie heute.

Ich glaube, Christoph ist gestern ein bisschen schnell über den Stoff hinweggegangen.

Er ist auf jeden Fall viel weiter gekommen, als ich mir vorgestellt habe, dass er kommen sollte, er könnte.

Darum wollen wir noch ein bisschen wiederholen, aber nur ein bisschen wiederholen.

Das, was er zusätzlich über das Skriptum hinausgehend erzählt hat, ein Teil davon ist in diesem Umdruck, den ich bitte da mitzunehmen, aber ich werde nicht nochmal darauf eingehen.

Zuletzt gesehen haben wir uns am 27. Mai und da haben wir festgestellt, dass ein Code mit zwei Codewörtern die Fehlerrate beliebig klein gemacht werden kann, die Wortfehlerrate, wenn nur dieses R0 positiv ist.

Weil ich kann dann den Erwartungswert über alle Codes so schreiben, als 2 hoch N minus R0, wobei N die Codewortlänge ist.

Insofern braucht man die Codewortlänge nur groß genug machen, dann wird es schon richtig werden.

Dieser Ausdruck, die Cutoff Rate, das ist die kleine Schwester der Kanalkapazität, das ist eine Gewirkgemessen in Bit pro Kanalbenutzung, weil es der Logorhythmus einer Wahrscheinlichkeit ist.

Wir müssen hier nur über alle möglichen Eingangssymbolen und über alle möglichen Ausgangssymbolen des Kanals addieren.

Da drin steht die Übergangsmatrix, die Elemente der Übergangsmatrix, mit welcher Wahrscheinlichkeit welches Symbol x i am Eingang in ein Symbol y j am Ausgang abgebildet wird.

Das ist also der Kanal, während das da rechts die A priori Wahrscheinlichkeit, das heißt mit welcher Wahrscheinlichkeit nutze ich welches Symbol, ob ich den Kanal vernünftig benutze oder nicht.

Deshalb maximieren wir das über die Eingangsverteilung, sodass es nur noch vom Kanal selbst abhängt, wie bei der Kapazität.

Diese kleine Schwester der Kanalkapazität, die Cutoff Rate, wurde bis etwa vor 20 Jahren als die Kanalkapazität für den Praktiker bezeichnet.

Inzwischen ist das überholt, es gibt Codes, die die Kanalkapazität wirklich erreichen. Aha, schaltet er nicht weiter.

Praktisch, gerade ist es noch gegangen. Mist, da liegt keine Maus dabei. Aha.

Abgestorben, Rechner, tot, tut nichts mehr.

Entschuldigung, gerade hat es noch funktioniert, hinten hergeschaltet alles, aber momentan abgestürzt. Warte, das hat es noch getan. Jetzt geht es wieder.

Aha, gut, haben wir Glück gehabt.

Ich weiß nicht, wo er gehängt ist. Vielleicht hat es auch mit diesem Windows-Kan nicht abgedatet. Nein, steht er wieder. Ich glaube, ich hänge.

Schreiben tut er. Aber umblättern kann ich nicht. Doch, jetzt kann ich umblättern. Kann ich so umblättern?

Okay, schauen wir mal, vielleicht funktioniert es. Ja, das definiert man als die Cutoff-Rate eines gedächtnislosen, behafteten Kanals.

Das wollen wir nicht näher berücksichtigen. Jetzt machen wir das mit vielen Codewörtern, nicht nur mit zwei Codewörtern, sondern eins mit vielen Codewörtern.

Entschuldigung für diese Unterbrechung. Wir verwenden, wie bei der ursprünglichen Ableitung der Batacaria baut, einfach die Union baut.

Ich sage, ein Codewort wird falsch, wenn es zum ersten oder zum zweiten oder zum dritten falschen verfälscht wird.

Wenn ich diese Wahrscheinlichkeiten einfach addiere, dann bekomme ich eine obere Schranke für die viele Wahrscheinlichkeiten.

Ich sage einfach, die Wahrscheinlichkeit, dass es falsch geht, ist die Summe aller Einzelwahrscheinlichkeiten, dass es vom richtigen Nüten zum Iten falschen geht,

wobei das I durchgezählt wird über alle Codewörter. Es gibt zwei hoch N mal R oder zwei hoch K Codewörter.

Aber ich darf nicht Nü sein, weil Nü ja das Richtige ist. Diesen Ausdruck können wir aber für Zufallscode berechnen.

Alle sind gleich, wir haben nur den Vorfaktor. Dann können wir bei diesem Vorfaktor noch diesen Einser vergessen, dann wird es noch größer.

Wir sehen also diesen Fehlerexponent jetzt als Funktion der Coderate. R0 minus R, einfach eine Geradete von R0 bis 0 abfällt an der Stelle R0 mit der Steigung minus 1.

Das ist der Batacaria-Fehler-Exponent. Das heißt, solange die Coderate kleiner ist als die Cutoff-Rate, ist dieser Teil vom Exponent positiv.

Insgesamt ist der Exponent negativ und ich brauche N, die Codewortlänge nur groß genug machen.

Der Erwartungswert der Fehlerwahrscheinlichkeit über alle Codes, die möglich sind, geht nach Null.

Wenn der Erwartungswert über alle Codes nach Null geht, dann gibt es mindestens einen Code, wo das auch gilt.

Wir kennen schlechte Codes.

Der Mittelwert ist im Gleichgewicht. Auf der einen Seite hängen die schlechten Codes, auf der anderen Seite hängen die guten.

Der Mittelwert ist gut. Wir kennen schlechte und im Mittel sind wir hier. Da muss es auch gute geben, sonst können wir nicht in der Balance sein.

Verstanden? Damit ist die Existenz von guten Codes gezeigt.

Das ist ein sehr zentraler Satz, das über einen gestörten Übertragungskanal mit beliebig hoher Zuverlässigkeit übertragen werden kann, wenn man die Coderate kleiner hält als die Cutoff-Rate.

Das ist aber noch nicht ganz alles, aber wir wollen ein bisschen über die Cutoff-Rate diskutieren. Sie ist nicht negativ und sie verschwindet nur dann, wenn auch die Kapazität verschwindet.

Die Cutoff-Rate ist immer kleiner oder gleich der Kapazität. Das können wir einfach dadurch sehen. Wir können bis zur Cutoff-Rate zuverlässig übertragen.

Wir haben aber gelernt, nach dem Umkehrung des Kanalkodierungstheoriums, dass größer wie die Cutoff-Rate eine Zuverlässigkeit als zuverlässige Übertragung grundsätzlich nicht möglich ist.

Dann würden sich die beiden Dinge widersprechen. Also ist die Cutoff-Rate immer kleiner als die Kapazität, weil sonst würde die Umkehrung des Kanalkodierungstheoriums außer Kraft gesetzt.

Bei symmetrischen Kanälen wird die Kapazität durch Gleichverteilung erreicht. Auch die Cutoff-Rate wird durch Gleichverteilung erreicht.

Mit binären Eingangssymbolen kann man das noch ganz einfach darstellen. Und das verrückte ist das, was für die Kapazität nicht gilt.

Bei binären Eingangssymbolen wird Cutoff-Rate immer für gleichwahrscheinlich, also ein halb für die beiden Eingangssymbolen maximiert.

Ok, da sieht man aber Beispiele. Die Kapazität eines binären Erasure-Channels ist 1 minus die Auslöschungswahrscheinlichkeit, während die Cutoff-Rate darunter läuft.

Klar, sie ist nicht negativ, sie wird nur dort null, wo auch die Kapazität null ist. Für den binary symmetric channel sind wir 1 minus die binäre Entropiefunktion, die Kapazität, und die Cutoff-Rate ist ein bisschen kleiner.